#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include <conio.h>

// ================== 常量与类型定义区 ==================
#define MAP_ROWS 21
#define MAP_COLS 20
#define DOT '.'
#define WALL '#'
#define EMPTY ' '
#define PACMAN 'P'
#define GHOST 'G'
#define NAME_LEN 16
#define GHOST_COUNT 4

/**
 * 表示地图上的一个坐标点。
 * r 表示行号（row），c 表示列号（column）。
 */
typedef struct {
    int r, c;  // r: 行号，c: 列号
} Point;

// --- 排行榜结构体 ---
/**
 * 表示排行榜中的一条记录。
 * name 为玩家姓名，score 为玩家得分。
 */
typedef struct {
    char name[NAME_LEN]; // 玩家姓名
    int score;          // 玩家得分
} LeaderboardEntry;



// ================== 数据结构层 ==================
// --- 队列（用于BFS，循环队列实现） ---
// QUEUE_MAX 定义循环队列的最大容量，等于地图的最大点数
#define QUEUE_MAX (MAP_ROWS * MAP_COLS)

/**
 * 循环队列结构体，用于BFS等场景。
 * data 存储队列中的点（Point），front 为队头索引，rear 为队尾索引。
 */
typedef struct {
    Point data[QUEUE_MAX]; // 队列数据数组
    int front, rear;      // 队头和队尾索引
} Queue;

/**
 * 初始化循环队列。
 * @param q 指向队列的指针。
 */
void queue_init(Queue* q) { q->front = q->rear = 0; }

/**
 * 判断循环队列是否为空。
 * @param q 指向队列的指针。
 * @return 如果队列为空返回1，否则返回0。
 */
int queue_empty(Queue* q) { return q->front == q->rear; }

/**
 * 判断循环队列是否已满。
 * @param q 指向队列的指针。
 * @return 如果队列已满返回1，否则返回0。
 */
int queue_full(Queue* q) { return (q->rear + 1) % QUEUE_MAX == q->front; }

/**
 * 向循环队列尾部插入一个点。
 * @param q 指向队列的指针。
 * @param p 要插入的点（Point结构体）。
 */
void queue_push(Queue* q, Point p) {
    if (queue_full(q)) return; // 可根据需要处理溢出
    q->data[q->rear] = p;
    q->rear = (q->rear + 1) % QUEUE_MAX;
}

/**
 * 从循环队列头部弹出一个点。
 * @param q 指向队列的指针。
 * @return 弹出的点（Point结构体）。
 */
Point queue_pop(Queue* q) {
    Point p = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX;
    return p;
}

// --- 排序（通用） ---

/**
 * 对排行榜数组按分数从高到低进行排序。
 * @param arr 排行榜数组。
 * @param n 数组长度。
 */
void sort(LeaderboardEntry* arr, int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j].score < arr[j+1].score) {
                LeaderboardEntry tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

// --- 链表（通用）结构体定义 ---
typedef struct {
    int r, c;
} Dot;  // 豆子或坐标结构体

typedef struct ListNode {
    Dot pos;                // 节点存储的豆子位置
    struct ListNode* next;  // 指向下一个节点
} ListNode;

typedef struct {
    ListNode* head; // 链表头指针
    int count;      // 链表节点数量
} LinkedList;

// --- 链表（通用） ---

/**
 * 初始化链表。
 * @param list 指向链表的指针。
 */
void LinkedList_init(LinkedList* list) {
    list->head = NULL;
    list->count = 0;
}

/**
 * 向链表头部插入一个节点。
 * @param list 指向链表的指针。
 * @param pos 要插入的Dot结构体（豆子位置）。
 */
void LinkedList_insert(LinkedList* list, Dot pos) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->pos = pos;
    node->next = list->head;
    list->head = node;
    list->count++;
}

/**
 * 从链表中移除指定位置的节点。
 * @param list 指向链表的指针。
 * @param pos 要移除的Dot结构体（豆子位置）。
 * @return 如果移除成功返回1，否则返回0。
 */
int LinkedList_remove(LinkedList* list, Dot pos) {
    ListNode* prev = NULL, *cur = list->head;
    while (cur) {
        if (cur->pos.r == pos.r && cur->pos.c == pos.c) {
            if (prev) prev->next = cur->next;
            else list->head = cur->next;
            free(cur);
            list->count--;
            return 1;
        }
        prev = cur;
        cur = cur->next;
    }
    return 0;
}

/**
 * 释放链表所有节点，重置链表。
 * @param list 指向链表的指针。
 */
void LinkedList_free(LinkedList* list) {
    ListNode* cur = list->head;
    while (cur) {
        ListNode* tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    list->head = NULL;
    list->count = 0;
}

// 自定义比较函数类型
typedef int (*CompareFunc)(void* a, void* b);

// --- 二叉树相关函数（通用） ---


// --- 二叉树结构体（通用） ---
/**
 * 二叉树节点结构体。
 * name 表示节点名称，left/right 分别为左、右子节点指针。
 */
typedef struct BinaryTreeNode {
    char name[16];                  // 节点名称，此处用来保存技能名称
    struct BinaryTreeNode* left;    // 左子节点
    struct BinaryTreeNode* right;   // 右子节点
} BinaryTreeNode;



/**
 * 创建一个二叉树节点。
 * @param name 节点名称。
 * @return 新创建的二叉树节点指针。
 */
BinaryTreeNode* BinaryTree_create(const char* name) {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    strcpy(node->name, name);
    node->left = node->right = NULL;
    return node;
}

/**
 * 将child节点插入到parent的左子树。
 * @param parent 父节点。
 * @param child 子节点。
 */
void BinaryTree_insert_left(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->left = child;
}

/**
 * 将child节点插入到parent的右子树。
 * @param parent 父节点。
 * @param child 子节点。
 */
void BinaryTree_insert_right(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->right = child;
}

/**
 * 递归释放二叉树所有节点。
 * @param root 根节点指针。
 */
void BinaryTree_free(BinaryTreeNode* root) {
    if (!root) return;
    BinaryTree_free(root->left);
    BinaryTree_free(root->right);
    free(root);
}

/**
 * 二叉树先序遍历（递归实现）。
 * @param root 根节点指针。
 */
void BinaryTree_preorder(BinaryTreeNode* root) {
    if (!root) return;
    BinaryTree_preorder(root->left);
    BinaryTree_preorder(root->right);
}

/**
 * 计算二叉树的最大深度。
 * @param root 根节点指针。
 * @return 最大深度。
 */
int BinaryTree_depth(BinaryTreeNode* root) {
    if (!root) return 0;
    int l = BinaryTree_depth(root->left);
    int r = BinaryTree_depth(root->right);
    return (l > r ? l : r) + 1;
}

/**
 * 计算二叉树节点总数。
 * @param root 根节点指针。
 * @return 节点总数。
 */
int BinaryTree_count(BinaryTreeNode* root) {
    if (!root) return 0;
    return 1 + BinaryTree_count(root->left) + BinaryTree_count(root->right);
}

/**
 * 计算二叉树叶子节点数量。
 * @param root 根节点指针。
 * @return 叶子节点数量。
 */
int BinaryTree_leaf_count(BinaryTreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return BinaryTree_leaf_count(root->left) + BinaryTree_leaf_count(root->right);
}

// --- 二叉树构造（技能树示例） ---
BinaryTreeNode* BinaryTree_sample() {
    BinaryTreeNode* root = BinaryTree_create("RootSkill");
    BinaryTreeNode* left = BinaryTree_create("Attack");
    BinaryTreeNode* right = BinaryTree_create("Defense");
    BinaryTreeNode* leftleft = BinaryTree_create("Accelerate");
    BinaryTreeNode* leftright = BinaryTree_create("More One Life");
    BinaryTreeNode* rightleft = BinaryTree_create("Cross Wall");
    BinaryTreeNode* rightright = BinaryTree_create("Unbeatable");
    BinaryTree_insert_left(root, left);
    BinaryTree_insert_right(root, right);
    BinaryTree_insert_left(left, leftleft);
    BinaryTree_insert_right(left, leftright);
    BinaryTree_insert_left(right, rightleft);
    BinaryTree_insert_right(right, rightright);
    return root;
}

// --- 图结构体与BFS ---
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
} Graph;

void graph_init(Graph* g, char grid[MAP_ROWS][MAP_COLS]) {
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            g->grid[i][j] = grid[i][j];
}

/**
 * 初始化前驱数组
 */
void init_pre(Point pre[MAP_ROWS][MAP_COLS]) {
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            pre[i][j].r = pre[i][j].c = -1;
}



/**
 * BFS主循环，负责遍历地图、判断终点、记录前驱。
 * @param g 指向图结构体。
 * @param start 起点坐标。
 * @param target 终点坐标。
 * @param vis 访问标记数组。
 * @param pre 前驱数组，用于路径回溯。
 * @return 若找到终点返回1，否则返回0。
 */
int bfs_core(Graph* g, Point start, Point target, int vis[MAP_ROWS][MAP_COLS], Point pre[MAP_ROWS][MAP_COLS]) {
    /*
    实现算法过程：
    1. 创建并初始化一个队列，将起点start入队，并标记为已访问。
    2. 进入循环，只要队列不为空就继续：
       a) 从队列头部弹出一个点p。
       b) 判断p是否为终点target，如果是则返回1（表示找到终点）。
       c) 对于p的四个相邻方向（上、下、左、右）：
          i. 计算新点的坐标(nr, nc)。
          ii. 判断新点是否在地图范围内，且不是墙，且未被访问。
          iii. 如果满足条件，将新点标记为已访问，记录前驱pre[nr][nc]=p，并将新点入队。
    3. 如果循环结束仍未找到终点，返回0（表示不可达）。
    */
    Queue q; queue_init(&q);
    vis[start.r][start.c] = 1;
    queue_push(&q, start);
    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    while (!queue_empty(&q)) {
        Point p = queue_pop(&q);
        if (p.r == target.r && p.c == target.c) return 1;
        for (int d = 0; d < 4; d++) {
            int nr = p.r + dr[d], nc = p.c + dc[d];
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS &&
                g->grid[nr][nc] != WALL && !vis[nr][nc]) {
                vis[nr][nc] = 1;
                pre[nr][nc] = p;
                queue_push(&q, (Point){nr, nc});
            }
        }
    }
    return 0;
}

/**
 * 路径回溯，根据前驱数组回溯最短路径。
 * @param start 起点坐标。
 * @param target 终点坐标。
 * @param pre 前驱数组。
 * @param path 用于存储回溯得到的路径。
 * @return 路径长度。
 */
int backtrack_path(Point start, Point target, Point pre[MAP_ROWS][MAP_COLS], Point* path) {
    int len = 0;
    Point cur = target;
    Point tmp_path[MAP_ROWS * MAP_COLS];
    while (!(cur.r == start.r && cur.c == start.c)) {
        tmp_path[len++] = cur;
        cur = pre[cur.r][cur.c];
    }
    tmp_path[len++] = start;
    for (int i = 0; i < len; i++) {
        path[i] = tmp_path[len-1-i];
    }
    return len;
}

/**
 * BFS查找最短路径，主函数。
 * 负责调用BFS主循环和路径回溯，返回最短路径长度。
 * @param g 指向图结构体。
 * @param start 起点坐标。
 * @param target 终点坐标。
 * @param path 用于存储最短路径的数组（可为NULL）。
 * @param path_len 用于存储路径长度的指针（可为NULL）。
 * @return 路径长度（若不可达返回0）。
 */
int graph_bfs(Graph* g, Point start, Point target, Point* path, int* path_len) {
    if (start.r == target.r && start.c == target.c) {
        if (path) path[0] = start;
        if (path_len) *path_len = 1;
        return 1;
    }
    int vis[MAP_ROWS][MAP_COLS] = {0};
    Point pre[MAP_ROWS][MAP_COLS];
    init_pre(pre);
    int found = bfs_core(g, start, target, vis, pre);
    if (!found) { if (path_len) *path_len = 0; return 0; }
    int len = backtrack_path(start, target, pre, path);
    if (path_len) *path_len = len;
    return len;
}



// ================== 逻辑层 ==================
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
    LinkedList dots;
} Map;

typedef struct {
    int row, col;
    int score;
    int lives;
} Pacman;

typedef struct {
    int row, col;
} Ghost;

static char map_data[MAP_ROWS][MAP_COLS+1] = {
    "####################",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..................#",
    "#..##..####..##...#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#.................#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..##..####..##...#",
    "#..................#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "####################"
};

void map_init(Map* map) {
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map_data[i][j];
            map->grid[i][j] = c;
        }
    }
    LinkedList_init(&map->dots);
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            if (map->grid[i][j] == DOT) {
                Dot pos = {i, j};
                LinkedList_insert(&map->dots, pos);
            }
        }
    }
}

int map_eat_dot(Map* map, int row, int col) {
    if (map->grid[row][col] != DOT) return 0;
    Dot pos = {row, col};
    int removed = LinkedList_remove(&map->dots, pos);
    if (removed) {
        map->grid[row][col] = EMPTY;
        return 1;
    }
    return 0;
}

void pacman_init(Pacman* p, int row, int col) {
    p->row = row; p->col = col; p->score = 0; p->lives = 3;
}

void ghost_init(Ghost* g, int row, int col) {
    g->row = row; g->col = col;
}

void pacman_draw(Pacman* p, Map* map) {
    map->grid[p->row][p->col] = PACMAN;
}

void ghost_draw(Ghost* g, Map* map) {
    map->grid[g->row][g->col] = GHOST;
}

void ghost_move(Map* map, Ghost* ghost, Pacman* pacman) {
    Graph g;
    graph_init(&g, map->grid);
    Point path[MAP_ROWS * MAP_COLS];
    int path_len;
    if (graph_bfs(&g, (Point){ghost->row, ghost->col}, (Point){pacman->row, pacman->col}, path, &path_len)) {
        if (path_len > 1) {
            ghost->row = path[1].r;
            ghost->col = path[1].c;
        }
    }
}

// ================== UI层 ==================
// Windows控制台设置函数
void setup_console() {
    // 获取控制台句柄
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    
    // 设置控制台字体
    CONSOLE_FONT_INFOEX fontInfo;
    fontInfo.cbSize = sizeof(fontInfo);
    GetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
    wcscpy(fontInfo.FaceName, L"Consolas");
    fontInfo.dwFontSize.Y = 16;
    SetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
}

// 使用ASCII字符定义墙体
const char* WALL_CHARS[] = {
    "+", // 十字
    "-", // 横线
    "|", // 竖线
    "+", // 左上
    "+", // 右上
    "+", // 左下
    "+", // 右下
    "+", // 左中
    "+", // 右中
    "+", // 上中
    "+"  // 下中
};

void map_draw(Map* map) {
    int ghost_color_idx = 0;
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    const WORD ghost_colors[] = {
        FOREGROUND_RED | FOREGROUND_INTENSITY,                    // 红色
        FOREGROUND_BLUE | FOREGROUND_INTENSITY,                   // 蓝色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY, // 黄色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY // 白色
    };

    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map->grid[i][j];
            if (c == WALL) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                int up = (i > 0 && map->grid[i-1][j] == WALL);
                int down = (i < MAP_ROWS-1 && map->grid[i+1][j] == WALL);
                int left = (j > 0 && map->grid[i][j-1] == WALL);
                int right = (j < MAP_COLS-1 && map->grid[i][j+1] == WALL);
                
                if (up || down) printf("|");
                else if (left || right) printf("-");
                else printf("+");
                
            } else if (c == DOT) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                printf(".");
            } else if (c == PACMAN) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
                printf("C");  // 使用C代表Pacman
            } else if (c == GHOST) {
                SetConsoleTextAttribute(hConsole, ghost_colors[ghost_color_idx]);
                printf("G");  // 使用G代表Ghost
                ghost_color_idx = (ghost_color_idx + 1) % 4;
            } else {
                printf(" ");
            }
        }
        printf("\n");
        ghost_color_idx = 0;
    }
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    printf("\nDots left: %d\n", map->dots.count);
}

void leaderboard_ui(LeaderboardEntry* lb, int n) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    sort(lb, n);
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+======== Leaderboard ========+\n");
    
    for (int i = 0; i < n; i++) {
        printf("| ");
        if (i == 0) {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        } else {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        }
        printf("%-10s | %4d", lb[i].name, lb[i].score);
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf(" |\n");
    }
    
    printf("+===========================+\n");
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

void binarytree_print_with_color(BinaryTreeNode* node, int depth, int isLast, int isRoot) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    for (int i = 0; i < depth; i++) {
        printf("| ");  // 改为竖线表示层级
    }
    if (depth > 0) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("|-");  // 统一使用|-连接
    }
    if (isRoot) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    } else {
        SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    }
    if (node->left && node->right) {
        binarytree_print_with_color(node->left, depth+1, 0, 0);
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    } else if (node->left) {
        binarytree_print_with_color(node->left, depth+1, 1, 0);
    } else if (node->right) {
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    }
}

void binarytree_ui(BinaryTreeNode* root) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+====== Skill Tree ======+\n");
    if (root)
        binarytree_print_with_color(root, 0, 1, 1);
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("+=======================+\n");
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Total Skills: ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_count(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Skills Level(Tree Depth): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_depth(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Real Powerful Skills(Leaf count): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_leaf_count(root));
}

// Windows版本的键盘输入检测
int kbhit() {
    return _kbhit();
}

// ================== 主函数 ==================
int main() {
    // 设置控制台
    setup_console();
    
    Map map;
    Pacman pacman;
    Ghost ghosts[GHOST_COUNT];
    LeaderboardEntry lb[5] = { {"Alice", 120}, {"Bob", 200}, {"Carol", 150}, {"You", 0}, {"Test", 0} };
    char playerName[NAME_LEN] = "You";
    
    srand(time(NULL));
    map_init(&map);
    pacman_init(&pacman, 10, 10);
    ghost_init(&ghosts[0], 1, 2);
    ghost_init(&ghosts[1], 1, 17);
    ghost_init(&ghosts[2], 19, 2);
    ghost_init(&ghosts[3], 19, 17);
    
    int frame = 0;
    int running = 1;
    
    while (running) {
        system("cls");  // Windows清屏命令
        
        for (int i = 0; i < MAP_ROWS; i++)
            for (int j = 0; j < MAP_COLS; j++)
                if (map.grid[i][j] == PACMAN || map.grid[i][j] == GHOST)
                    map.grid[i][j] = EMPTY;
        
        pacman_draw(&pacman, &map);
        for (int i = 0; i < GHOST_COUNT; i++)
            ghost_draw(&ghosts[i], &map);
        
        map_draw(&map);
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        printf("\nName: %s  Score: %d  Lives: %d\n", playerName, pacman.score, pacman.lives);
        
        if (kbhit()) {
            char key = _getch();
            int dr = 0, dc = 0;
            if (key == 'w' || key == 'W') dr = -1;
            if (key == 's' || key == 'S') dr = 1;
            if (key == 'a' || key == 'A') dc = -1;
            if (key == 'd' || key == 'D') dc = 1;
            int nr = pacman.row + dr, nc = pacman.col + dc;
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS && map.grid[nr][nc] != WALL) {
                pacman.row = nr; pacman.col = nc;
                if (map_eat_dot(&map, nr, nc)) pacman.score += 10;
            }
        }
        
        if (frame % 2 == 0) {
            for (int i = 0; i < GHOST_COUNT; i++) {
                ghost_move(&map, &ghosts[i], &pacman);
                if (ghosts[i].row == pacman.row && ghosts[i].col == pacman.col) {
                    pacman.lives--;
                    if (pacman.lives <= 0) running = 0;
                }
            }
        }
        
        if (map.dots.count == 0) running = 0;
        Sleep(120);  // Windows睡眠函数，单位为毫秒
        frame++;
    }
    
    printf("\nGame Over!\n");
    lb[3].score = pacman.score;
    leaderboard_ui(lb, 5);
    BinaryTreeNode* skillroot = BinaryTree_sample();
    binarytree_ui(skillroot);
    BinaryTree_free(skillroot);
    LinkedList_free(&map.dots);
    
    // 恢复默认颜色
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    return 0;
}